import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * 有一种兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子。
 * 例子：假设一只兔子第3个月出生，那么它第5个月开始会每个月生一只兔子。
 * 一月的时候有一只兔子，假如兔子都不死，问第n个月的兔子总数为多少？
 * 3 ---> 2.
 */

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int n = sc.nextInt();
            System.out.println(Fibonacci2(n));
        }
    }
    private static final Map<Long, Long> filter = new HashMap<>(); //filter过滤的意思
    // 这个map的key值为斐波那契的项数, val值为其对应的值.
    public static long Fibonacci2(long n) {
        if(n <= 1) { return n; }
        if(n == 2) { return 1; }

        // 先计算 n-2 的递归 再计算 n-1 的递归会更好一些~~
        long pPre; // 表示 n-2
        if(filter.containsKey(n-2)) {
            // 在map中找到了n-1 说明已经进行过了 n-2 的递归
            pPre = filter.get(n-2);
        } else {
            // 没找到 将第n-1 和 其对应的结果放入 map中.
            pPre = Fibonacci2(n-2);
            filter.put(n-2,pPre);
        }

        long pre; // 表示 n-1
        if(filter.containsKey(n-1)) {
            // 在map中找到了n-1 说明已经进行过了 n-1 的递归
            pre = filter.get(n-1);
        } else {
            // 没找到 将第n-1 和 其对应的结果放入 map中.
            pre = Fibonacci2(n-1);
            filter.put(n-1,pre);
        }

        return pre + pPre;
    }
}